﻿// 38杨氏矩阵
//内容：有一个数字矩阵，矩阵的每行从左到右都是递增的，矩阵从上到下都是递增的
//请编写程序在这样的矩阵中，查找某个数字是否存在
//要求：时间复杂度小于O（N）

#include <stdio.h>

int FindNum(int arr[3][3], int k, int *px, int *py)
{
	int x = 0;            //第0行，最后一列
	int y = *py - 1;      //即是一行中的最大数，又是一列中的最小数
	while (x <= *px - 1 && y >= 0)
	{
		if (arr[x][y] > k)
		{
			y--;             //即k小于一行中最大值，从倒数第二列找
		}
		else if (arr[x][y] < k)
		{
			x++;                  //K大于与一行中最大值，从下一行去找
			
		}
		else
		{
			*px = x;                  //K大于与一行中最大值，从下一行去找
			*py = y;
			return 1;
		}
	}
	return 0;
}
int main()
{
	int arr[3][3] = { {1,2,3},{4,5,6},{7,8,9} };
	int k = 10;
	int x = 3;
	int y = 3;
	int ret = FindNum(arr, k, &x, &y);
	if (ret == 1)
	{
		printf("找到了\n");
		printf("下表是：%d %d\n", x, y);
	}
	else
	{
		printf("找不到\n");
	}
	return 0;
}

